﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace CompilerForC.LexicalAnalysis
{
    /// <summary>
    /// Enumerates special symbols, each serving as a placeholder for the 
    /// specific set of characters.
    /// </summary>
    internal enum CharacterSet
    {
        /// <summary>
        /// Placeholder for any character.
        /// </summary>
        Any,
        /// <summary>
        /// Placeholder for digit.
        /// </summary>
        Digit,
        /// <summary>
        /// Placeholder for alphabetic character.
        /// </summary>
        Alpha,
    }

    /// <summary>
    /// Type of the key for the transition table.
    /// </summary>
    internal struct TransitionTableKey : IEquatable<TransitionTableKey>
    {
        #region Private Fields

        /// <summary>
        /// State for which transition is defined.
        /// </summary>
        private char _state;
        /// <summary>
        /// Symbol for which transition is defined.
        /// </summary>
        private char _symbol;
        /// <summary>
        /// Character set for which transition is defined.
        /// </summary>
        private CharacterSet _charSet;

        #endregion Private Fields

        #region Constructors

        /// <summary>
        /// Constructs transition table key for specified state and symbol.
        /// </summary>
        /// <param name="state">State for which transition will be applied.</param>
        /// <param name="symbol">Symbol for which transition will be applied.</param>
        public TransitionTableKey(char state, char symbol)
        {
            _state = state;
            _symbol = symbol;
            _charSet = default(CharacterSet);
        }

        /// <summary>
        /// Constructs transition table key for specified state and character set.
        /// </summary>
        /// <param name="state">State for which transition will be applied.</param>
        /// <param name="characterSet">Set of characters for which transition will be applied.</param>
        public TransitionTableKey(char state, CharacterSet characterSet)
        {
            _state = state;
            _symbol = char.MaxValue;
            _charSet = characterSet;
        }

        #endregion Constructors

        #region Object Members

        /// <summary>
        /// Performs equality test between transition table keys.
        /// </summary>
        /// <param name="obj">Object.</param>
        /// <returns>True if keys are equal, false otherwise.</returns>
        public override bool Equals(object obj)
        {
            return GetType() == obj.GetType() && Equals((TransitionTableKey)obj);
        }

        /// <summary>
        /// Obtains hash code for the transition table key.
        /// </summary>
        /// <returns>Hash code.</returns>
        public override int GetHashCode()
        {
            return _state;
        }

        #endregion Object Members
        
        #region IEquatable<TransitionTableKey> Members

        /// <summary>
        /// Performs equality test between transition table keys.
        /// </summary>
        /// <param name="other">Other transition table key.</param>
        /// <returns>True if keys are equal, false otherwise.</returns>
        public bool Equals(TransitionTableKey other)
        {
            return _state.Equals(other._state) && _symbol.Equals(other._symbol) && _charSet.Equals(other._charSet);
        }

        #endregion
    }


    /// <summary>
    /// Lexer support class.
    /// Encapsulates deterministic finite automaton used to validate string 
    /// patterns.
    /// </summary>
    internal class StateMachine
    {
        #region Private Fields

        /// <summary>
        /// Initial state.
        /// </summary>
        private char _startState;
        /// <summary>
        /// Current state.
        /// </summary>
        private char _currentState;
        /// <summary>
        /// Sets of states that are considered valid.
        /// </summary>
        private HashSet<char> _validStates = new HashSet<char>();
        /// <summary>
        /// Transition table.
        /// </summary>
        private Dictionary<TransitionTableKey, char> _transitionTable = new Dictionary<TransitionTableKey, char>();

        #endregion Private Fields

        #region Public Properties

        /// <summary>
        /// Gets or sets initial state.
        /// </summary>
        public char StartState
        {
            get { return _startState; }
            set { _startState = value; }
        }

        /// <summary>
        /// Gets current state.
        /// </summary>
        public char CurrentState
        {
            get { return _currentState; }
        }

        /// <summary>
        /// Gets set of states that are considered valid.
        /// </summary>
        public HashSet<char> ValidStates
        {
            get { return _validStates; }
        }

        /// <summary>
        /// Gets transition table.
        /// </summary>
        public Dictionary<TransitionTableKey, char> TransitionTable
        {
            get { return _transitionTable; }
        }

        #endregion Public Properties

        #region Constructor

        /// <summary>
        /// Constructs state machine with no states or transitions defined.
        /// </summary>
        public StateMachine()
        {
        }

        #endregion Constructor

        #region Public Methods

        /// <summary>
        /// Resets current state and validates specified input string against 
        /// the transition table.
        /// </summary>
        /// <param name="input">String to validate.</param>
        /// <returns>True if transitions were applied for each character of the 
        /// input string, and current state of the state machine ends within 
        /// valid states. False otherwise.</returns>
        public bool Validate(string input)
        {
            Debug.Assert(input != null, "Parameter 'input' can not be null.");

            // Reset current state to start state.
            _currentState = _startState;

            // For each symbol in the input string...
            foreach (char inputSymbol in input)
            {
                // ...try to apply transition and change current state.
                char newState;

                if (!TryGetNewState(inputSymbol, out newState)) {
                    return false;
                }

                _currentState = newState;
            }

            // String is successfully validated if current state is within valid states.
            return _validStates.Contains(_currentState);            
        }

        #endregion Public Methods

        #region Private Methods

        /// <summary>
        /// Tries to retrieve new state for the current state and the specified 
        /// input symbol. State can be only retrieved if transition table has 
        /// entry for the current state and the specified input symbol.
        /// </summary>
        /// <param name="inputSymbol">Input symbol.</param>
        /// <param name="newState">Returns new state if suitable transition is 
        /// found.</param>
        /// <returns>True if suitable transition is found, false otherwise.</returns>
        private bool TryGetNewState(char inputSymbol, out char newState)
        {
            // Try get state for the non-special character...
            if (_transitionTable.TryGetValue(new TransitionTableKey(_currentState, inputSymbol), out newState)) 
            {
                return true;
            }
            // Try get state for the special character...
            else
            {
                if (_transitionTable.TryGetValue(new TransitionTableKey(_currentState, CharacterSet.Any), out newState)) 
                    return true;
                if (_transitionTable.TryGetValue(new TransitionTableKey(_currentState, CharacterSet.Digit), out newState) && char.IsDigit(inputSymbol)) 
                    return true;
                if (_transitionTable.TryGetValue(new TransitionTableKey(_currentState, CharacterSet.Alpha), out newState) && char.IsLetter(inputSymbol)) 
                    return true;
            }

            return false;
        }

        #endregion Private Methods
    }
}
